/*
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表


输入：head = [4,2,1,3]
输出：[1,2,3,4]

利用快慢指针找到链表中点后，对链表进行归并排序

*/

//
class Solution
{
public:
    ListNode *sortList(ListNode *head)
    {
        return sortList(head, nullptr); //
    }

    //传入链表头尾指针
    ListNode *sortList(ListNode *head, ListNode *tail)
    {
        if (head == nullptr)
        {
            return head;
        }
        if (head->next == tail)
        {
            head->next = nullptr;
            return head;
        }

        //找中点
        ListNode *slow = head, *fast = head;
        while (fast != tail)
        {
            slow = slow->next;
            fast = fast->next; //试探一步，不是null再走一步
            if (fast != tail)
            {
                fast = fast->next;
            }
        }
        ListNode *mid = slow; //中点

        return merge(sortList(head, mid), sortList(mid, tail));
    }

    //
    ListNode *merge(ListNode *head1, ListNode *head2)
    {
        ListNode *dummyHead = new ListNode(0);
        ListNode *temp = dummyHead, *temp1 = head1, *temp2 = head2;
        
        //
        while (temp1 != nullptr && temp2 != nullptr)
        {
            if (temp1->val <= temp2->val)
            {
                temp->next = temp1;
                temp1 = temp1->next;
            }
            else
            {
                temp->next = temp2;
                temp2 = temp2->next;
            }
            temp = temp->next; //
        }
        
        if (temp1 != nullptr)
        {
            temp->next = temp1;
        }
        else if (temp2 != nullptr)
        {
            temp->next = temp2;
        }
        return dummyHead->next;
    }
};
